public class MyHashMap {
    public class Node{
        public int val;
        public int key;
        public Node next;

        public Node(int val, int key) {
            this.val = val;
            this.key = key;
        }
    }
    public Node[] map;//哈希表
    public int size;//元素个数
    public double factor=0.75;//负载因子
    //初始化
    public MyHashMap(){
        this.map=new Node[8];
        this.size=0;
    }

    //存储
    public int put(int key,int val){
        int index=key%map.length;//关键字 模 数组长度，
        Node cur=map[index];//得到存储链表的头
        while(cur!=null){//遍历链表
            if(key==cur.key){//找到与关键字相同的节点
                int tmp=cur.val;//保存旧节点数据域
                cur.val=val;//更新旧节点数据域
                return tmp;//返回跟新前的数据
            }
            cur=cur.next;
        }
        Node node=new Node(val,key);//无相同关键字,创建一个新的节点。
        node.next=map[index];//头插的形式链接到链表头部
        map[index]=node;//链表头更新位置
        this.size++;//集合长度+1
        if(factor<=loadFactor()){//判断是否超出负载因子
            resize();//超出就扩容
        }
        return -1;
    }

    //扩容
    public void resize(){
        Node[] newMap=new Node[map.length*2];//扩容不可以直接拷贝扩容。先得到一个2倍长度的集合
        for(int i=0;i<map.length;i++){//遍历旧集合中数组
            Node cur=map[i];//从旧集合中每个链表的头开始遍历每一个节点
            Node next;//保存cur的下一个节点，防止更新后找不到旧集合中链表的下一个节点，断链。
            while(cur!=null){//遍历链表
                next=cur.next;//保存cur的下一个节点
                int index=cur.key%newMap.length;//找到一个新的合理的数组位置
                cur.next=newMap[index];//链表形式头插存入到新的集合中
                newMap[index]=cur;//链表头更新
                cur=next;//指向下一个
            }
        }
        map=newMap;//更新
    }

    //计算负载因子
    public double loadFactor(){
        return this.size*1.0/map.length;//计算负载因子的公式
    }

    //获取
    public int get(int key){
        int index=key%this.map.length;//得到数组下标
        for(Node cur=map[index];cur!=null;cur=cur.next){//遍历链表
            if(cur.key==key){//找到与关键字相同的节点
                return cur.val;//返回数据域
            }
        }
        return -1;//没找到
    }
}
